This unit introduces a fundamentally different clustering algorithm:
DBSCAN.
Unlike the methods discussed earlier, DBSCAN identifies clusters from local density and can
explicitly flag noise or outlier points. We will see how it discovers clusters of
arbitrary shape and how to select its hyperparameters MinPts and
\( \varepsilon \) (epsilon) using the K-distance graph.
Learning Objectives
List and define the three DBSCAN point types: core, border, noise
State DBSCAN's core definitions: directly density-reachable, density-reachable, density-connected
Manually execute DBSCAN on a small 2D dataset given MinPts and ε
Use the rule-of-thumb for MinPts (≥ d+1) and the K-distance elbow method to tune ε
Compare DBSCAN vs K-Means across 8+ dimensions: K-choice, shape, outliers, etc.
For each cluster \(C_j\), the average silhouette width is the mean of the individual
silhouette values for the points in that cluster:
\[
\bar{s}(C_j) = \frac{1}{|C_j|} \sum_{d_i \in C_j} s(i)
\]
The global average silhouette width is then
\[
\text{ASW} = \frac{1}{n} \sum_{i=1}^{n} s(i)
\]
These averages summarize cluster quality at both the individual-cluster and overall levels.
Computationally, silhouette is expensive for large datasets (O(n²) distance evaluations).
2.5 DBSCAN — Density-Based Spatial Clustering of Applications with Noise
DBSCAN assigns each data point to one of three point types based on two hyperparameters:
the radius ε (epsilon) and the minimum number of points MinPts required for a dense
neighborhood. The three types are core, border, and noise points.
1. Core Points
2. Border Points
3. Noise Points
A point q is a core point if its ε-neighborhood contains at least MinPts points (counting q itself).
Property: Core points lie in the interior of a dense region and serve as the "seeds" from which clusters are grown.
A point p is a border point if its own ε-neighborhood contains < MinPts points, but there is a chain of direct density-reachability links from a core point to p.
Property: Border points lie at the edge of a dense region. They belong to a cluster, but they cannot extend that cluster further.
A point is a noise point (outlier) if it is neither a core point nor reachable from any core point.
Property: In sklearn, noise points are explicitly assigned a cluster label of −1. Thus, DBSCAN can leave such points outside all discovered clusters.
2.6 DBSCAN Key Definitions
Directly density-reachable: p is directly density-reachable from q if:
q is a core point, AND
p is within ε of q (p ∈ N_ε(q)).
Note: "directly reachable" is NOT symmetric. A core can reach a border, but a border cannot reach back because it is not a core point.
Density-reachable: p is density-reachable from q if there exists a chain of
points q → q₁ → q₂ → … → q_k → p such that each adjacent step is directly density-reachable.
This relation is still asymmetric in general.
Density-connected: p and q are density-connected if there exists some core point o such that BOTH p and q are density-reachable from o.
This relation is symmetric and captures the "same cluster" relationship.
A DBSCAN cluster: A maximal set of density-connected points.
2.7 DBSCAN Example 1: Manual Execution
Consider the 5 2D points A(1,4), B(2,3), C(1,5), D(5,5), and E(8,1), with
MinPts = 2 and ε = 2 (using Euclidean distance).
Step 0: Identify the core points. For each point, count the points in its ε-neighborhood (distance ≤ 2), including the point itself:
A(1,4): dist to B = √((1)²+(-1)²)=√2≈1.41; to C=√(0+1)=1.0; to D=√16+1≈4.12; to E≈√58≈7.6. Neighborhood: {A,B,C} (size 3 ≥ 2). → A is CORE.
B(2,3): to A≈1.41, to C=√(1+4)=√5≈2.24 >2, to D≈3.6, to E≈6.3. Neighborhood: {B,A} (size 2 ≥ 2). → B is CORE because the count includes B itself.
C(1,5): to A=1.0, to B≈2.24, to D≈4.0. Neighborhood: {C,A}=2 → CORE.
D(5,5): to A≈4.12, to B≈3.6, to C≈4.0, to E≈5.0. Neighborhood: {D}=1 < 2 → NOT core.
E(8,1): distances huge. Only itself → NOT core.
Step 1: Grow the cluster from the core points. Starting from a core point, include points that are directly density-reachable within ε and continue the expansion through core points.
Start with core A and create Cluster 1. Add A, then expand to B and C, which are directly reachable. Because B and C are already core points and have no new points within ε, the expansion is complete.
D has no other neighbors besides itself, so mark it as noise.
E has no other neighbors besides itself, so mark it as noise.
Point
Coordinates
Type
Final Label
A
(1, 4)
Core
Cluster 1
B
(2, 3)
Core
Cluster 1
C
(1, 5)
Core
Cluster 1
D
(5, 5)
Noise
−1 (noise)
E
(8, 1)
Noise
−1 (noise)
2.8 Selecting DBSCAN Hyperparameters
Selecting MinPts
Rule of thumb: MinPts ≥ (dimensionality + 1), where d = number of features.
For 2D data: MinPts ≥ 3 (common pick: 4).
For higher dimensions: MinPts ≥ 4 or 5 as a start.
Larger MinPts:
It is more robust to noise/outliers.
It may merge smaller dense patches, reducing granularity.
As a standard starting heuristic, use MinPts = 4 or 5, then tune.
Selecting ε via the K-Distance Graph
For each point in the dataset, compute the distance to its k-th nearest neighbor,
with k = MinPts (or k = MinPts − 1 depending on convention). Then sort all the resulting
k-distances in ascending order and plot them. Use the elbow of this curve to
choose ε.
Points in dense regions (cluster members): the k-th nearest neighbor is close, so the k-distance is small.
Points in sparse regions (outliers / noise): the k-th nearest neighbor is far, so the k-distance is large.
Elbow: this is the transition region where distances "jump" from small (inliers) to large (outliers). Choose ε near that jump.
Iris K-distance Graph Case Study
With eps=0.2 and MinPts=5 on scaled Iris, all points become noise (label=-1), indicating that ε is too small.
Using the k-distance elbow method on Iris (k ≈ MinPts−1), pick ε ≈ 0.8 at the bend.
Running DBSCAN with ε=0.8 and MinPts=5 discovers two clusters with very few noise points.
Why 2 clusters instead of 3? The PCA visualization of Iris shows two major dense regions in feature space: Setosa is well-separated, while Versicolor and Virginica partially overlap.
2.9 DBSCAN vs K-Means: Side-by-Side
Aspect
K-Means
DBSCAN
Requires K specified beforehand?
Yes
No (discovers K automatically from density structure)
Assumes spherical / convex clusters?
Yes (centroid + SSE)
No (finds arbitrarily shaped clusters — even nested / crescent shapes)
Sensitive to outliers?
Very (outliers pull centroids toward them)
Robust (explicitly marks outliers as noise / −1)
Forces every point into a cluster?
Yes (hard assignment)
No (points can remain as noise)
Struggles with arbitrary / non-convex shapes?
Yes (splits them unnaturally)
Excellent at non-convex and nested shapes
Memory usage
Low
Needs distance matrix or spatial index (can be high)
Speed / Scalability
Very fast (linear in n × iter)
Slower (range queries needed)
Interpretable cluster centers?
Yes (centroids are meaningful)
No real "center" (harder to explain to business stakeholders)
3. Interactive Examples
Example 1: Purity of "one cluster per point"
A student claims "I can always achieve perfect purity, regardless of the dataset."
Is this possible? If yes, construct it. If not, explain.
Yes, trivially: set K = n (each point its own singleton cluster).
In each singleton cluster, the single point has exactly one true label, so
max_j |C_i ∩ L_j| = 1 for every cluster. Sum of maxima = n, so Purity = n/n = 1.
The result shows why purity alone is misleading: splitting the data into more clusters
can make the score look perfect without reflecting useful clustering structure.
Therefore, use it together with Adjusted Rand Index, Silhouette, or metrics that penalize
the use of more clusters.
Example 2: DBSCAN MinPts Intuition
A 7-dimensional dataset is to be clustered with DBSCAN. Which MinPts value is the
most reasonable starting point: 1, 2, 4, or 100?
Reveal Answer
MinPts = 4. The rule of thumb: MinPts ≥ d+1 = 8, but 4 is close and a
standard starting value (MinPts ≥ 4 or 5 for high dim). The choices illustrate the
trade-off: very small values make neighborhoods too permissive, while a very large
value can make dense regions fail the MinPts requirement. Why not the others?
MinPts = 1: every point is its own "core" → degenerate; every point forms its own cluster / no structure.
MinPts = 2: borderline; very sensitive to noise.
MinPts = 100: too large — many truly dense regions will have fewer than 100 neighbors within any reasonable ε → everything becomes noise.
This makes MinPts an important density threshold: the chosen value affects whether local neighborhoods are treated as sufficiently dense to form clusters.
Example 3: K-Means vs DBSCAN on two moons
The classic "two interleaved half-moons" dataset has two non-convex crescent-shaped
clusters. Which algorithm will recover the two moons correctly, and why?
DBSCAN will recover the two moons perfectly (with appropriate MinPts and ε):
Each crescent is a uniformly dense region → within each moon, every interior point is a core; the entire crescent is density-connected.
Between the two crescents there's a gap → no density bridge → DBSCAN correctly separates them into two clusters.
The key point is that DBSCAN follows the density-connected structure of the data rather than forcing each cluster to be represented by a centroid.
K-Means with K=2 will fail: it splits each crescent through the middle and produces two "half-moon sliced" clusters, because the centroids migrate to the overall arithmetic means of each half of the plane, which don't respect the shape.
Example 4: Rand Index edge case — perfect clustering
True labels: 4 points form 2 natural classes. Clustering produced also 2 clusters
identical to the true classes. What is the Rand Index? (Compute explicitly.)
Reveal Answer
Points: p1,p2 in L1; p3,p4 in L2. Same for clusters C1={p1,p2}, C2={p3,p4}.
As expected, every pair has the same relationship in the produced clustering and the true labels, so the Rand Index reaches 1.
4. Numerical Solutions
Problem 1: Purity from 3×2 contingency table
Contingency table (rows = produced clusters, cols = true labels):
Cluster
Label X
Label Y
Total
C1
8
2
10
C2
3
7
10
C3
5
5
10
Label total
16
14
n = 30
Compute the Purity from the contingency table.
📘 Step-by-Step Solution
Step 1: Find the largest class count in each cluster.
C1: max(8,2) = 8
C2: max(3,7) = 7
C3: max(5,5) = 5 (ties broken arbitrarily since value is same)
Step 2: Sum the maxima to obtain 8 + 7 + 5 = 20.
Step 3: Divide by n:
\[
\text{Purity} = \frac{20}{30} \approx 0.667
\]
Problem 2: DBSCAN class identification
Consider six 1D points on a number line at positions {1, 2, 3, 6, 10, 11}.
Use MinPts=3 and ε=1.2 (distance = absolute difference). Classify each point as
Core, Border, or Noise, and then list the clusters found.
📘 Step-by-Step Solution
Step 1: For each point, count points within ε=1.2 (including itself).
Point
Pos
Neighbors (|x − pos| ≤ 1.2)
Count
Core?
p1
1
{1,2}
2 < 3
No
p2
2
{1,2,3}
3 ≥ 3
✅ YES CORE
p3
3
{2,3}
2 < 3
No
p4
6
{6}
1 < 3
No
p5
10
{10,11}
2 < 3
No
p6
11
{10,11}
2 < 3
No
Step 2: Distinguish border points from noise. p2 is the only core point.
p1 is within ε of core p2 (|1−2|=1 ≤ 1.2) → Border of the same cluster.
p3 is within ε of core p2 (|3−2|=1 ≤ 1.2) → Border.
p4 is not a core, and its distance to the nearest core (p2) is 4 > 1.2, so no core can reach it → Noise.
p5 is at distance 8 from p2, so it is not reachable from the only core → Noise.
p6 is at distance 9 from p2, so it is not reachable from the only core → Noise.
Clusters found: One cluster, Cluster 1 = {p1, p2, p3}; the remaining points are noise: {p4, p5, p6} (label -1). This final grouping follows directly from the single core point and the two border points reachable from it.
Interpretation: Rand 0.5 is essentially random-level agreement on this tiny dataset. Jaccard is 0 because the produced clustering put no pair together that should have been together. The two metrics therefore agree that the clustering shows little useful pairwise agreement with the true labels.
5. Try It Yourself
Practice 1: Purity calculation 2×3
Contingency table (clusters × labels):
Red
Green
Blue
Total
Cluster A
9
1
1
11
Cluster B
1
8
5
14
Total
10
9
6
25
Compute the Purity and round the result to 3 decimals.
For Cluster A, the largest class count is max(9,1,1) = 9.
For Cluster B, the largest class count is max(1,8,5) = 8.
The sum is 17, with n = 25.
\[
\text{Purity} = \frac{17}{25} = 0.680
\]
Practice 2: DBSCAN MinPts=4
Consider the 2D points A(0,0), B(1,0), C(0,1), D(1,1), and E(5,5), with
ε=1.5 and MinPts=4. Classify each point and describe the resulting clusters.
Consider the ε-radius around each point:
A: N includes A,B,C,D (distances: 0, 1, 1, √2 ≈ 1.41 ≤ 1.5), giving 4 points ≥ 4 → Core.
B: its neighbors are A, B, D, C (same distances), giving 4 → Core.
C: its neighbors are A, C, D, B (same distances), giving 4 → Core.
D: its neighbors are A, B, C, D, giving 4 → Core.
E(5,5): the distance to the nearest others is √((5−1)²+(5−1)²) ≈ 5.66 > 1.5, so only itself is in its ε-neighborhood. It is NOT core and is not reachable from any core. → Noise.
Result: One cluster = {A,B,C,D}; E is noise (−1). The four nearby points reinforce one another's core status, while E has no connection to that dense region.
Practice 3: Adjusted Rand intuition via Rand baseline
We'll skip the exact ARI formula in this course and explain it qualitatively:
If RI = 0.86 on a dataset, why might the Adjusted Rand Index (ARI) be only 0.58,
and why do we prefer the adjusted version?
The plain Rand Index is dominated by TN (pairs that both methods put in different
groups). In typical datasets with many classes, MOST pairs are in different true
classes, and MOST pairs are also in different clusters — so even random clusterings
can have a high Rand index merely by "mostly saying no." This makes RI less informative
when the large number of TN pairs dominates the score.
The Adjusted Rand Index (ARI) corrects this by subtracting the expected RI
under a random-partition baseline and normalizing, so that ARI ≈ 0 for random
independent partitions and ARI = 1 only for perfect agreement. This makes the adjusted
score more useful when we want agreement beyond what can be attributed to the
random-partition baseline. This is why ARI (and not plain RI) is the standard in
scikit-learn's adjusted_rand_score.
6. Interactive Quiz
Your score: 0 / 5
7. Key Takeaways
DBSCAN has 3 point types: Core (≥ MinPts in an ε-ball), Border (in a core's ε-ball but not a core), and Noise (−1, everything else). This point taxonomy determines whether a point helps grow a cluster, belongs to its boundary, or remains outside all clusters.
DBSCAN key relationships: directly density-reachable (core→within ε), density-reachable (chain of direct), and density-connected (mutually reachable from some core, symmetric → defines a cluster). These relationships explain how local density links individual points into a cluster.
Set MinPts ≥ d+1 (typically 4 or 5). Set ε from the elbow of the sorted k-distance (k ≈ MinPts) curve where dense regions transition to sparse outliers. The elbow is useful because it marks the change from the small distances typical of dense regions to the larger distances of sparse points.
DBSCAN auto-discovers K, handles arbitrary shapes, and marks outliers explicitly; K-Means requires K, assumes spherical clusters, and forces every point into a cluster. The comparison is therefore mainly about how each method defines and assigns clusters.
8. Common Pitfalls
Forgetting to count the point ITSELF in MinPts: "ε-neighborhood size ≥ MinPts" includes the query point. A point with 2 other neighbors within ε counts MinPts=3, not 2. This detail directly affects whether the point is classified as core.
Misunderstanding "directly density-reachable" as symmetric: It is not. A border point is within ε of a core (core→border is "direct"), but the reverse step is invalid because the border is not itself a core.
Running DBSCAN on unscaled data: ε is a Euclidean radius, so feature scales matter. StandardScaler / MinMaxScaler first. Otherwise, the same ε can represent very different neighborhoods across features.
Picking ε too small / too large: Too small → almost everything is noise (−1); too large → all dense points merge into one giant cluster. Use the K-distance elbow rather than guessing.
Rand Index dominance by TNs: With many classes, TN dominates RI, making random-looking splits score high anyway. Prefer ARI when TN dominance makes the plain RI hard to interpret.